Elementos de teoría de números

Divisibilidad

Definición [Divisibilidad]

Un entero $b$ es divisible por un entero $a$, no cero, si existe un entero $x$ tal que $b = ax$ y se escribe $a\mid b$. En el caso que en que $b$ no sea divisible por $a$ se escribe $a\nmid b$

Teorema [Propiedades de divisibilidad] i. $a\mid b$ $\Rightarrow$ $a\mid bc,\ \forall c\in\mathbb{Z}$ ii. Si $a\mid b$ y $b\mid c$ $\Rightarrow$ $a\mid c$ iii. Si $a\mid b$ y $a\mid c$ $\Rightarrow$ $a\mid bx+cy,\ \forall x,y\in\mathbb{Z}$ (**Ejemplo**) iv. Si $a\mid b$ y $b\mid a$ $\Rightarrow$ $a=\pm b$ v. Si $a\mid b$ y $a> 0$, $b>0$ $\Rightarrow$ $a\leq b$

Algoritmo de la división

Teorema [El algoritmo de la división]

Si $b$ y $a$ son enteros, con $a\neq 0$. Existen enteros $q$ y $r$ tal que $$b = qa +r,\quad 0\leq r<|a|$$

Dependiendo de la literatura, se pueden encontrar diferentes formas del resultado anterior

Ejemplo

$b=34$, $a =7$
$b=-25$ $a=-4$
$b=-24$, $a=5$

Máximo común divisor

Un entero $c$ es un divisor común de $a$ y $b$ si $c\mid a$ y $c\mid b$

Definición [Máximo común divisor] Para enteros $a$, $b$, (por lo menos uno diferente de cero) el máximo común divisor $\mathrm{mcd}(a,b)$ ($\mathrm{gcd}(a,b)$) de $a$ y $b$ es el entero positivo más grande que divide a $a$ y a $b$. Un entero no negativo $d$ es el **máximo común divisor** de los enteros $a$ y $b$ si: 1. $d$ es un divisor común de $a$ y $b$ 2. Si $c\mid a$ y $c\mid b$ $\Rightarrow$ $c\mid d$
Ejemplo

$b=10$, $a =15$
$b=-50$ $a=20$
$b=-24$, $a=5$

Teorema [Combinación mcd]

Si $d = \mathrm{mcd}(a,b)$ entonces existen enteros $s$ y $t$ tal que $$d = sa + tb$$

Ejemplo

$gcd(10,15)=5$
$gcd(-50,20)=10$
$gcd(-24,5)=1$
$gcd(2299,627)=209$

Pareja
Actividad: Máximo común divisor

Algoritmo Euclideano

Teorema [Algoritmo Euclideano]

Dados los enteros $a$ y $b$ con $a>0$, se hace una aplicación repetida del algoritmo de la división, para obtener una serie de ecuaciónes $$ \begin{aligned} b &=q_{1} a+r_{1} & 0< r_1

Dependiendo de la literatura, se pueden encontrar diferentes formas del resultado anterior

Pareja
Ejemplo

$gcd(10,15)=5 = (-1)10 +(1)15$
$gcd(-50,20)=10= (-1)(-50) +(-2)20$
$gcd(-24,5)=1= (1)(-24) +(5)5$
$gcd(2299,627)=209= (-1)2299 +(4)627$

Mínimo común múltiplo

Los enteres $a$, $b$, diferentes de cero, tienen un multiplo común $c$ si $a\mid c$ y $b\mid c$

Definición [Mínimo común múltiplo] Un entero no negativo $c$ es el mínimo común multiplo de los enteros $a$ y $b$ ($mcm(a,b)=lcm(a,b)=c$) si:
1. $a\mid c$ y $b\mid c$
2. Si $a\mid d$ y $b\mid d$ $\Rightarrow$ $c\mid d$

Un resultado que se tiene es: $mcd(a,b)mcm(a,b)=|ab|$

Ejemplo

$lcm(10,15)=30$
$lcm(-50,20)=100$
$lcm(-24,5)=128$
$lcm(2299,627)=6897$

Números primos

Definición [Número primo]

Se dice que un número $p>1$ es un número primo, en caso que no exista divisor $d$ de $p$ que satisfaga $11$ no es un primo, entonces se dice que es un número compuesto.

Primos relativos

Teorema [Divisibilidad con primos]

Si $p\mid a_1a_2\dots a_n$ entonces $p$ divide por lo menos a un factor $a_i$ del producto.

Definición [Primos relativos]

Enteros positivos $a$ y $b$ se dicen qeu son primos relativos (o coprimos) si $\mathrm{mcd}(a,b)=1$

Teorema [Descomposición en primos]

Todo entero $n>1$ puede expresarse como un producto de primos.

Función totient de Euler

Definición [Función totient de Euler]

La función totient de Euler $\phi:\mathbb{Z}^+\rightarrow\mathbb{N}$, dado $n$, $\phi(n)$ es el numero de enteros positivos menores a iguales a $n$ que son coprimos con $n$

Propiedades

Actividad: Totient de Euler

Teorema fundamental de la aritmética

Teorema [Fundamental de la aritmética]

La factorización de cualquier entero positivo $n$ en primos es única independientemente del orden de los primos.

Teorema [Euclides]

El cantidad de número primos es infinita

Teorema [Ubicación de los números primos]

Existen arbitrariamente grandes vacios en la serie de los números primos.

Aritmética modular

Definición [Congruencia] Sean $a,b, m\in \mathbb{Z}$, con $m\neq 0$. Si $m$ divide a la diferencia de $a-b$, se dice que $a$ es congruente con $b$ módulo $m$ y se escribe $$a\equiv b \bmod m$$

Notas:

Ejemplos

$ \begin{aligned} &25=4 \bmod 7 \\ &6=1 \bmod 5 \\ &5=5 \bmod 6 \\ &-25=3 \bmod 7 \\ &-6=4 \bmod 5 \\ &-18=0 \bmod 6 \end{aligned} $

Def

La operación modulo genera clases de equivalencia

Propiedades de la suma:

Propiedad de multiplicación:

Porpiedad de potencias:

Teorema [Propiedades congruencias]

Supóngase que $a,b,c,d,x,y\in \mathbb{Z}$, entonces:

a. $a\equiv b \bmod m$, $b\equiv a \bmod m$ y $a-b\equiv 0 \bmod m$ son porposiciones equivalentes
b. Si $a\equiv b \bmod m$ y $b\equiv c \bmod m$, entonces $a\equiv c \bmod m$
c. Si $a\equiv b \bmod m$ y $c\equiv d \bmod m$, entonces $ax +cy \equiv bx +dy \bmod m$
d. Si $a\equiv b \bmod m$ y $c\equiv d \bmod m$, entonces $ac \equiv bd \bmod m$
e. Si $a\equiv b \bmod m$ y $d\mid m$, $d>0$, entonces $a\equiv b \bmod d$

Teorema [Pequeño teorema de Fermat]

Si $p$ es un número primo y $r$ es un entero con $\mathrm{gcd}(r,p)=1$ entonces \begin{equation} r^{p-1}\equiv 1\bmod p \label{fermat} \end{equation}

Problemas

  1. Demuestra que si $x\equiv y (\bmod m)$ entonces $x \pm k\equiv y\pm k (\bmod m)$ para $k\in\mathbb{Z}$. ¿Que propiedad es un caso particular de este echo?

  2. Construye gráficas para visualizar la sigueinte aproximación asintótica para $\pi(x)$
    $$\lim_{x\rightarrow\infty}\pi(x)\frac{\ln(x)}{x} = 1$$

  3. Sea un numero con $n+1$ digitos $z = d_n\dots d_0$. LA representación en base $10$ de este número es $$z=d_n\dots d_0 = \sum_{i=0}^n d_i\times 10^i$$ Ahora si recordamos que $$(a + b)^i= a^i + K_{i-1}a^{i-1}b+\dots+K_{1}ab^{i-1}+b^i$$ si pensemos en la descomposición de $10$ como $10 = a+b$, entonces $$z = d_n\dots d_0 = \sum_{i=0}^n d_i\times (a+b)^i$$ Veamos las condiciones para que $z$ sea divisble entre $a$. Por las descomposición del binomio, casi todos los términos son necesariamente divisibles por $a$, excepto los siguientes términos (¿Por qué?) $$r =\sum_{i=0}^n d_i\times b^i$$ Entonces para revisar la divisibilida de $z$ por $a$, basta ver bajo que condiciones $r$ es divible por $a$, esto dependera como se descomponga a $10=a+b$.

    Por ejemplo, si decomponemos $10$ como $10 = 5+5$, al analizar $r$, casi todos sus terminos (excepto uno) necesariamente son sivisibles por $5=b$, pero $d_0\times b^0 = d_0$ no necesarimente es divible por $5$ al menos que $d_0 = 0$ 0 $d_0=5$, así

    Un número $z\in\mathbb{Z}$ es divisible por 5, si termina en $0$ o $5$

    Deduce una regla para las sigueintes divisibilidades
    1. Divisibilidad con $2$
    2. Divisibilidad con $3$
    3. Divisibilidad con $4$
    4. Divisibilidad con $6$
    5. Divisibilidad con $7$
    6. Divisibilidad con $8$
    7. Divisibilidad con $9$
    8. Divisibilidad con $10$
    9. Divisibilidad con $11$
  4. Sea $ E\left(\mathbb{Z}_7\right)=\{(4, 4), (4, 3), (1, 0), (3, 2), (3, 5)\}\cup\{\mathcal{O}\}\subset\mathbb{Z}_7\times\mathbb{Z}_7$. Sea $P_1,P_2\neq \mathcal{O}$ puntos en $E$, con $P_1 = (x_1,y_1)$ y $P_2=(x_2,y_2)$. Se define

    1. Si $x_1\neq x_2$, entonces $P_1+P_2 = (x_3,y_3)$ con
    $$ \begin{aligned} x_{3} &=\left[s^{2}-x_{1}-x_{2} \bmod 7\right] \quad \text { y } \quad y_{3}=\left[s \cdot\left(x_{1}-x_{3}\right)-y_{1} \bmod 7\right], \\ \text { donde } s &=\left[\frac{y_{2}-y_{1}}{x_{2}-x_{1}} \bmod 7\right] . \end{aligned} $$
    2. Si $x_1=x_2$ pero $y_1\neq y_2$ entonces $P_1=-P_2$

    3. Si $P_1 = P_2$ y $y_1\neq 0$, entonces $P_1+P_2 =2P_1 = (x_3,y_3)$ con
    $$ \begin{aligned} x_{3} &=\left[s^{2}-x_{1}-x_{2} \bmod 7\right] \quad \text { y } \quad y_{3}=\left[s \cdot\left(x_{1}-x_{3}\right)-y_{1} \bmod 7\right], \\ \text { donde } s &=\left[\frac{3x_{1}^2+3}{2y_1} \bmod 7\right] . \end{aligned} $$
    4. Si $P_1=P_2$ y $y_1=0$ entonces $P_1+P_2=\mathcal{O}$
    Sen sabe que con la operación antes definida $+:E\left(\mathbb{Z}_7\right)\times E\left(\mathbb{Z}_7\right)\rightarrow E\left(\mathbb{Z}_7\right)$, la tupla $(E\left(\mathbb{Z}_7\right),+)$ es un grupo.

    a) construye la tabla de operación de este grupo finito. Sugerencia: Escribe un programa para esto
    b) ¿El grupo es abeliano?
    c) ¿El grupo es ciclico?
    d) ¿A que grupo, con estrutura de suma más sencilla, es isomorfo?

    $\left(E(\mathbb{Z}_7),+\right)$ es el grupo de curva-elliptica de $E\left(\mathbb{Z}_7\right)$, este tipo de grupos son utilizados ampliamente en criptografia, debido a la alta seguridad qeu porporcionan.
  5. Si $c\mid ab$ y $\gcd(a,c)=1$, entonces $c\mid b$
  6. Si $a\mid N$, $b\mid N$, y $\gcd(a,b)=1$ entonces $ab\mid N$
  7. Demuestra que $a\equiv b\bmod m$ si y solo si $[a\bmod m]=[b\bmod m]$